UVa/10003 - Cutting sticks/10003.2.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <algorithm>
   4 #include <climits>
   5 #include <vector>
   6
   7 using namespace std;
   8
   9 typedef pair<int,int> point;
  10
  11 vector<int> p;
  12 int cache[1001][1001];
  13
  14 int f(point n){
  15   int i = n.first, j = n.second;
  16   //  cout << "n: " << n.first << " " << n.second << endl;
  17   if (cache[i][j] != -1){
  18     //cout << "Retornando " << cache[n] << endl;
  19     return cache[i][j];
  20   }
  21   //first < second
  22   if (n.second < n.first) swap(n.first, n.second);
  23
  24   for (int k=0; k<p.size()-1; ++k){
  25     if (p[k]<=n.first && n.first<=p[k+1] &&
  26         p[k]<=n.second && n.second<=p[k+1]){
  27       //cout << "Retornando 0" << endl;
  28       return cache[i][j] = 0;
  29     }
  30   }
  31
  32   int min=INT_MAX;
  33   for (int k=0; k<p.size(); ++k){
  34     if (n.first<p[k] && p[k]<n.second){
  35       int q = n.second - n.first + f(point(n.first, p[k])) + f(point(p[k], n.second));
  36       //cout << "q es: " << q << endl;
  37       if (q < min){
  38         min = q;
  39       }
  40     }
  41   }
  42   //cout << "min es: " << min << endl;
  43   //cout << "Retornando " << min << endl;
  44   return   cache[i][j] = min;
  45
  46 }
  47
  48 int main(){
  49   int l;
  50   while (cin >> l && l > 0){
  51     int n;
  52     cin >> n;
  53     memset(cache, -1, sizeof(cache));
  54     p = vector<int>(n+2);
  55     p[0] = 0;
  56     p[n+1] = l;
  57     for (int i=1; i<=n; ++i){
  58       cin >> p[i];
  59     }
  60     cout << "The minimum cutting is " << f(point(0, l)) << ".\n";
  61   }
  62   return 0;
  63 }